<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<meta name="generator" content="Doxygen 1.8.11"/>
<title>GrPPI: Map/reduce pattern</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="search/searchdata.js"></script>
<script type="text/javascript" src="search/search.js"></script>
<script type="text/javascript">
  $(document).ready(function() { init_search(); });
</script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr style="height: 56px;">
  <td id="projectlogo"><img alt="Logo" src="logo.svg"/></td>
  <td id="projectalign" style="padding-left: 0.5em;">
   <div id="projectname">GrPPI
   &#160;<span id="projectnumber">0.2</span>
   </div>
   <div id="projectbrief">Generic and Reusable Parallel Pattern Interface</div>
  </td>
 </tr>
 </tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.8.11 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "search",false,'Search');
</script>
  <div id="navrow1" class="tabs">
    <ul class="tablist">
      <li><a href="index.html"><span>Main&#160;Page</span></a></li>
      <li class="current"><a href="pages.html"><span>Related&#160;Pages</span></a></li>
      <li><a href="modules.html"><span>Modules</span></a></li>
      <li><a href="namespaces.html"><span>Namespaces</span></a></li>
      <li><a href="annotated.html"><span>Classes</span></a></li>
      <li><a href="files.html"><span>Files</span></a></li>
      <li>
        <div id="MSearchBox" class="MSearchBoxInactive">
        <span class="left">
          <img id="MSearchSelect" src="search/mag_sel.png"
               onmouseover="return searchBox.OnSearchSelectShow()"
               onmouseout="return searchBox.OnSearchSelectHide()"
               alt=""/>
          <input type="text" id="MSearchField" value="Search" accesskey="S"
               onfocus="searchBox.OnSearchFieldFocus(true)" 
               onblur="searchBox.OnSearchFieldFocus(false)" 
               onkeyup="searchBox.OnSearchFieldChange(event)"/>
          </span><span class="right">
            <a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.png" alt=""/></a>
          </span>
        </div>
      </li>
    </ul>
  </div>
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
     onmouseover="return searchBox.OnSearchSelectShow()"
     onmouseout="return searchBox.OnSearchSelectHide()"
     onkeydown="return searchBox.OnSearchSelectKey(event)">
</div>

<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="javascript:void(0)" frameborder="0" 
        name="MSearchResults" id="MSearchResults">
</iframe>
</div>

</div><!-- top -->
<div class="header">
  <div class="headertitle">
<div class="title">Map/reduce pattern </div>  </div>
</div><!--header-->
<div class="contents">
<div class="textblock"><p>The <b>map/reduce</b> pattern combines a <b>map</b> and <b>reduce</b> operation in a single pattern. In a <b>map/reduce</b> operation, firstly one or more input data sets are <em>mapped</em> by applying a transformation operation. Then, the results are combined by means of a reduction operation.</p>
<p>The interface to the <b>map/reduce</b> pattern is provided by function <code><a class="el" href="group__mapreduce__pattern__native.html#ga7e52d3b07cbe4ae9928f2ad607d70e46" title="Invoke Map/reduce pattern on a data sequence with native parallel execution. ">grppi::map_reduce()</a></code>. As all functions in <em>GrPPI</em>, this function takes as its first argument an execution policy.</p>
<div class="fragment"><div class="line"><a class="code" href="group__mapreduce__pattern__native.html#ga7e52d3b07cbe4ae9928f2ad607d70e46">grppi::map_reduce</a>(exec, other_arguments...);</div></div><!-- fragment --><p><b>Note</b>: A <b>map/reduce</b> could be also expressed by the composition of a <b>map</b> and a <b>reduce</b>. However, <b>map/reduce</b> may fuse both stages, allowing for extra optimizations.</p>
<h2>Map/reduce variants</h2>
<p>There are several variants:</p>
<ul>
<li><em>Unary map/reduce</em>: A <b>map/reduce</b> taking a single input sequence.</li>
<li><em>N-ary map/reduce</em>: A <b>map/reduce</b> taking multiple input sequences that are combined during the <em>map</em> stage.</li>
</ul>
<h2>Key elements in a map/reduce</h2>
<p>There are two central elements of a <b>map/reduce</b>: the <b>Transformer</b> used for the <em>map</em> stage, and the <b>Combiner</b> used for the <em>reduce</em> stage.</p>
<p>A <b>Transformer</b> may be a <b>UnaryTransformer</b> or a <b>MultiTransformer</b>.</p>
<p>A <b>UnaryTransformer</b> is any C++ callable entity that takes a data item and transforms it. The input type and the output type may differ. Thus, a unary transformer <code>op</code> is any operation that, given an input <code>x</code> of type <code>T</code> and output type <code>U</code>, makes valid the following:</p>
<div class="fragment"><div class="line">U res = op(x);</div></div><!-- fragment --><p>A <b>MultiTransformer</b> is any C++ callable entity that takes data items, one of each input sequence, and transforms them into an output value. The input types and the output type may differ. Thus, a multi-transformer <code>op</code> is any operation that, given the inputs <code>x1, x2, ... , xN</code> of types <code>T1, T2, ... , TN</code> and an output type <code>U</code>, makes valid the following:</p>
<div class="fragment"><div class="line">U res = op(x1, x2, ..., xN);</div></div><!-- fragment --><p>A <b>Combiner</b> is any C++ callable entity, that is able to combine two values into a single value. A Combiner <code>cmb</code> is any operation taking two values <code>x</code> and <code>y</code> of types <code>T</code> and <code>U</code> and returning a combined value of type <code>T</code>, making valid the following:</p>
<div class="fragment"><div class="line">T x;</div><div class="line">U y;</div><div class="line">T res = cmb(x,y);</div></div><!-- fragment --><h2>Details on map/reduce variants</h2>
<h3>Unary map_reduce</h3>
<p>An unary <b>map/reduce</b> takes a single data set and performs consecutively the <b>map</b> and the <b>reduce</b> stages, returning the reduced value.</p>
<p>The only interface currently offered for this pattern is based on iterators (following the C++ standard library conventions):</p>
<ul>
<li>The input data set is specified by two iterators.</li>
</ul>
<p>A unary <b>map/reduce</b> also requires an identity value for the <b>Combiner</b>. </p><hr/>
<p> <b>Example</b>: Transforms a sequence of strings to its corresponding double values and computes the addition of those values. </p><div class="fragment"><div class="line">vector&lt;string&gt; v { <span class="stringliteral">&quot;1.0&quot;</span>, <span class="stringliteral">&quot;2.0&quot;</span>, <span class="stringliteral">&quot;3.5&quot;</span>, <span class="stringliteral">&quot;0.25&quot;</span> };</div><div class="line"><span class="keyword">auto</span> res = <a class="code" href="group__mapreduce__pattern__native.html#ga7e52d3b07cbe4ae9928f2ad607d70e46">grppi::map_reduce</a>(exec,</div><div class="line">  begin(v), end(v),</div><div class="line">  0.0,</div><div class="line">  [](<span class="keywordtype">string</span> s) { <span class="keywordflow">return</span> stod(s); },</div><div class="line">  [](<span class="keywordtype">double</span> x, <span class="keywordtype">double</span> y) { <span class="keywordflow">return</span> x+y; }</div><div class="line">);</div><div class="line"><span class="comment">// res == 6.75</span></div></div><!-- fragment --><hr/>
<h3>N-ary map/reduce</h3>
<p>A n-ary <b>map/reduce</b> takes multiple data sets and performs consecutively the <b>map</b> and <b>reduce</b> stages, returning the reduced value.</p>
<p>The only interface currently offered for this pattern is based on iterators (following the C++ standard library conventions):</p>
<ul>
<li>The first data set is specified by two iterators.</li>
<li>All the other input data sets are specified by iterators to the start of the input data sequences, assuming that the size of all sequences are, at least, as large as the first sequence.</li>
</ul>
<p>A n-ary <b>map/reduce</b> also requires an identity value for the <b>Combiner</b>. </p><hr/>
<p> <b>Example</b>: Compute scalar vector between two vectors of doubles. </p><div class="fragment"><div class="line">v = get_first_vector();</div><div class="line">w = get_second_vector();</div><div class="line"><span class="keyword">auto</span> res = <a class="code" href="group__mapreduce__pattern__native.html#ga7e52d3b07cbe4ae9928f2ad607d70e46">grppi::map_reduce</a>(exec,</div><div class="line">  begin(v), end(v),</div><div class="line">  0.0,</div><div class="line">  [](<span class="keywordtype">double</span> x, <span class="keywordtype">double</span> y) { <span class="keywordflow">return</span> x*y; },</div><div class="line">  [](<span class="keywordtype">double</span> x, <span class="keywordtype">double</span> y) { <span class="keywordflow">return</span> x+y; },</div><div class="line">  begin(w)</div><div class="line">);</div></div><!-- fragment --><hr/>
<h2>Additional examples of <b>map/reduce</b></h2>
<hr/>
<p> <b>Example</b>: Count word appearances in text lines. </p><div class="fragment"><div class="line">vector&lt;string&gt; words = get_words();</div><div class="line"><span class="keyword">auto</span> result = <a class="code" href="group__mapreduce__pattern__native.html#ga7e52d3b07cbe4ae9928f2ad607d70e46">grppi::map_reduce</a>(ex,</div><div class="line">  words.begin(), words.end(), map&lt;string,int&gt;{},</div><div class="line">  [](<span class="keywordtype">string</span> word) -&gt; map&lt;string,int&gt; { <span class="keywordflow">return</span> {{word, 1}}; },</div><div class="line">  [](map&lt;string,int&gt; &amp; lhs, <span class="keyword">const</span> map&lt;string,int&gt; &amp; rhs) -&gt; map&lt;string,int&gt; &amp; {</div><div class="line">    <span class="keywordflow">for</span> (<span class="keyword">auto</span> &amp; w : rhs) {</div><div class="line">      lhs[w.first]+= w.second;</div><div class="line">    }</div><div class="line">    <span class="keywordflow">return</span> lhs;</div><div class="line">  }</div><div class="line">);</div></div><!-- fragment --><hr/>
 </div></div><!-- contents -->
<!-- start footer part -->
<hr class="footer"/><address class="footer"><small>
Generated by &#160;<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/>
</a> 1.8.11
</small></address>
</body>
</html>
